class Solution:

    """
    方法： lengthOfLongestSubstring

    逻辑: 使用滑动窗口技术来查找给定字符串中最长的无重复字符子串的长度。

    Args:
        s (str): 输入字符串。

    Returns:
        int: 无重复字符的最长子串的长度。

    Time:  
        O(N)，其中 N 是字符串的长度。每个字符最多被访问两次（一次在右指针，另一次在左指针）。

    Space:  
        O(min(M, N)) = O(1)，其中 M 是字符集的大小（例如，ASCII 字符集为 128），N 是字符串的长度。我们使用一个哈希表来存储字符及其索引。
    """
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, res, i = {}, 0, -1
        for j in range(len(s)):
            if s[j] in dic:
                i = max(dic[s[j]], i) # 更新左指针 i
            dic[s[j]] = j # 哈希表记录
            res = max(res, j - i) # 更新结果
        return res

    """
    方法： lengthOfLongestSubstring1

    逻辑: 使用动态规划的方法来查找给定字符串中最长的无重复字符子串的长度。

    Args:
        s (str): 输入字符串。

    Returns:
        int: 无重复字符的最长子串的长度。

    Time:  
        O(N)，其中 N 是字符串的长度。每个字符最多被访问一次。

    Space:  
        O(M)，其中 M 是字符集的大小（例如，ASCII 字符集为 128）。使用一个哈希表来存储字符及其索引。
    """
    def lengthOfLongestSubstring1(self, s: str) -> int:
        dic = {}
        res = tmp = 0
        for j in range(len(s)):
            i = dic.get(s[j], -1) # 获取索引 i
            dic[s[j]] = j # 更新哈希表
            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]
            res = max(res, tmp) # max(dp[j - 1], dp[j])
        return res

    """
    方法： lengthOfLongestSubstring2

    逻辑: 使用滑动窗口和集合来查找给定字符串中最长的无重复字符子串的长度。

    Args:
        s (str): 输入字符串。

    Returns:
        int: 无重复字符的最长子串的长度。

    Time:  
        O(N)，其中 N 是字符串的长度。每个字符最多被访问两次。

    Space:  
        O(M)，其中 M 是字符集的大小（例如，ASCII 字符集为 128）。使用一个集合来维护当前窗口内的字符。
    """
    def lengthOfLongestSubstring2(self, s: str) -> int:
        ans = left = 0
        window = set()  # 维护从下标 left 到下标 right 的字符
        for right, c in enumerate(s):
            # 如果窗口内已经包含 c，那么再加入一个 c 会导致窗口内有重复元素
            # 所以要在加入 c 之前，先移出窗口内的 c
            while c in window:  # 窗口内有 c
                window.remove(s[left])
                left += 1  # 缩小窗口
            window.add(c)  # 加入 c
            ans = max(ans, right - left + 1)  # 更新窗口长度最大值
        return ans
    
    def test_lengthOfLongestSubstring1(self):
        """
        测试 lengthOfLongestSubstring1 方法

        测试用例包含:
        1. 普通字符串，包含重复字符
        2. 空字符串
        3. 单字符字符串
        4. 无重复字符的字符串
        5. 全部字符都相同的字符串
        """
        test_cases = [
            ("abcabcbb", 3),
            ("", 0),
            ("a", 1), 
            ("abcde", 5),
            ("bbbbb", 1),
            ("pwwkew", 3)
        ]

        for s, expected in test_cases:
            result = self.lengthOfLongestSubstring1(s)
            print(f"Input: {s}")
            print(f"Expected: {expected}")
            print(f"Got: {result}")
            print(f"{'Pass' if result == expected else 'Fail'}\n")

if __name__ == "__main__":
    solution = Solution()
    solution.test_lengthOfLongestSubstring1()